export function permuteUnique(nums: number[]): number[][] {
    const ret: number[][] = [];
    const path: number[] = [];
    const used: boolean[] = new Array(nums.length).fill(false);

    backTrace(nums, path, used, ret);

    return ret;
};

function backTrace (nums: number[], path: number[], used: boolean[], ret: number[][]) {
    if (path.length === nums.length) {
        ret.push([...path]);
        return;
    }
    
    const set = new Set<number>();
    for (let i = 0; i < nums.length; i++) {
        // 如果在上一层使用过，则继续
        if (used[i]) continue;
        // 如果在本层使用过，则继续
        if (set.has(nums[i])) continue;

        set.add(nums[i]);
        used[i] = true;
        path.push(nums[i]);
        backTrace(nums, path, used, ret);
        used[i] = false;
        path.pop();
    }
}